SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Prefix code</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Prefix code</span></span>

</h1>

</header>

<p>A <b>prefix code</b> is a type of <a href="Code" title="Code">code</a> system distinguished by its possession of the <b>prefix property</b>, which requires that there is no whole <a href="Code_word_(communication)" title="Code word (communication)">code word</a> in the system that is a <a href="Prefix_(computer_science)" class="mw-redirect" title="Prefix (computer science)">prefix</a> (initial segment) of any other code word in the system. It is trivially true for fixed-length codes, so only a point of consideration for <a href="Variable-length_code" title="Variable-length code">variable-length codes</a>.

</p><p>For example, a code with code {9, 55} has the prefix property; a code consisting of {9, 5, 59, 55} does not, because "5" is a prefix of "59" and also of "55". A prefix code is a <a href="Uniquely_decodable_code" class="mw-redirect" title="Uniquely decodable code">uniquely decodable code</a>: given a complete and accurate sequence, a receiver can identify each word without requiring a special marker between words. However, there are uniquely decodable codes that are not prefix codes; for instance, the reverse of a prefix code is still uniquely decodable (it is a suffix code), but it is not necessarily a prefix code.

</p><p>Prefix codes are also known as <b>prefix-free codes</b>, <b>prefix condition codes</b> and <b>instantaneous codes</b>. Although <a href="Huffman_coding" title="Huffman coding">Huffman coding</a> is just one of many algorithms for deriving prefix codes, prefix codes are also widely referred to as "Huffman codes", even when the code was not produced by a Huffman algorithm. The term <b>comma-free code</b> is sometimes also applied as a synonym for prefix-free codes<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> but in most mathematical books and articles (e.g.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>) a comma-free code is used to mean a <a href="Self-synchronizing_code" title="Self-synchronizing code">self-synchronizing code</a>, a subclass of prefix codes.

</p><p>Using prefix codes, a message can be transmitted as a sequence of concatenated code words, without any <a href="Out-of-band_data" title="Out-of-band data">out-of-band</a> markers or (alternatively) special markers between words to <a href="Framing_(telecommunication)" class="mw-redirect" title="Framing (telecommunication)">frame</a> the words in the message. The recipient can decode the message unambiguously, by repeatedly finding and removing sequences that form valid code words. This is not generally possible with codes that lack the prefix property, for example {0, 1, 10, 11}: a receiver reading a "1" at the start of a code word would not know whether that was the complete code word "1", or merely the prefix of the code word "10" or "11"; so the string "10" could be interpreted either as a single codeword or as the concatenation of the words "1" then "0".

</p><p>The variable-length <a href="Huffman_coding" title="Huffman coding">Huffman codes</a>, <a href="Country_calling_codes" class="mw-redirect" title="Country calling codes">country calling codes</a>, the country and publisher parts of <a href="ISBN" title="ISBN">ISBNs</a>, the Secondary Synchronization Codes used in the <a href="UMTS" title="UMTS">UMTS</a> <a href="W-CDMA" class="mw-redirect" title="W-CDMA">W-CDMA</a> 3G Wireless Standard, and the <a href="Instruction_set" class="mw-redirect" title="Instruction set">instruction sets</a> (machine language) of most computer microarchitectures are prefix codes.

</p><p>Prefix codes are not <a href="Error-correcting_codes" class="mw-redirect" title="Error-correcting codes">error-correcting codes</a>. In practice, a message might first be compressed with a prefix code, and then encoded again with <a href="Channel_coding" class="mw-redirect" title="Channel coding">channel coding</a> (including error correction) before transmission.

</p><p>For any <a href="Variable-length_code#Uniquely_decodable_codes" title="Variable-length code">uniquely decodable</a> code there is a prefix code that has the same code word lengths.<sup id="cite_ref-LTU2015_5-0" class="reference"><a href="#cite_note-LTU2015-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> <a href="Kraft's_inequality" class="mw-redirect" title="Kraft's inequality">Kraft's inequality</a> characterizes the sets of code word lengths that are possible in a <a href="Variable-length_code#Uniquely_decodable_codes" title="Variable-length code">uniquely decodable</a> code.<sup id="cite_ref-BRS75_6-0" class="reference"><a href="#cite_note-BRS75-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Techniques">Techniques</h2></div>

<p>If every word in the code has the same length, the code is called a <b>fixed-length code</b>, or a <b>block code</b> (though the term <a href="Block_code" title="Block code">block code</a> is also used for fixed-size <a href="Error-correcting_code" class="mw-redirect" title="Error-correcting code">error-correcting codes</a> in <a href="Channel_coding" class="mw-redirect" title="Channel coding">channel coding</a>). For example, <a href="ISO_8859-15" class="mw-redirect" title="ISO 8859-15">ISO 8859-15</a> letters are always 8 bits long. <a href="UTF-32/UCS-4" class="mw-redirect" title="UTF-32/UCS-4">UTF-32/UCS-4</a> letters are always 32 bits long. <a href="Asynchronous_Transfer_Mode" title="Asynchronous Transfer Mode">ATM cells</a> are always 424 bits (53 bytes) long. A fixed-length code of fixed length <i>k</i> bits can encode up to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{k}}</annotation>

</semantics>

</math></span><img src="./2d82641ae2702b0db07dd11830af27b9ee0cd196.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.251ex; height:2.676ex;" alt="{\displaystyle 2^{k}}" loading="lazy"></span> source symbols.

</p><p>A fixed-length code is necessarily a prefix code. It is possible to turn any code into a fixed-length code by padding fixed symbols to the shorter prefixes in order to meet the length of the longest prefixes. Alternately, such padding codes may be employed to introduce redundancy that allows autocorrection and/or synchronisation. However, fixed length encodings are inefficient in situations where some words are much more likely to be transmitted than others.

</p><p><a href="Truncated_binary_encoding" title="Truncated binary encoding">Truncated binary encoding</a> is a straightforward generalization of fixed-length codes to deal with cases where the number of symbols <i>n</i> is not a power of two. Source symbols are assigned codewords of length <i>k</i> and <i>k</i>+1, where <i>k</i> is chosen so that <i>2<sup>k</sup> < n ≤ 2<sup>k+1</sup></i>.

</p><p><a href="Huffman_coding" title="Huffman coding">Huffman coding</a> is a more sophisticated technique for constructing variable-length prefix codes. The Huffman coding algorithm takes as input the frequencies that the code words should have, and constructs a prefix code that minimizes the weighted average of the code word lengths. (This is closely related to minimizing the entropy.) This is a form of <a href="Lossless_data_compression" class="mw-redirect" title="Lossless data compression">lossless data compression</a> based on <a href="Entropy_encoding" class="mw-redirect" title="Entropy encoding">entropy encoding</a>.

</p><p>Some codes mark the end of a code word with a special "comma" symbol (also called a <a href="Sentinel_value" title="Sentinel value">Sentinel value</a>), different from normal data.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> This is somewhat analogous to the spaces between words in a sentence; they mark where one word ends and another begins. If every code word ends in a comma, and the comma does not appear elsewhere in a code word, the code is automatically prefix-free. However, reserving an entire symbol only for use as a comma can be inefficient, especially for languages with a small number of symbols. <a href="Morse_code" title="Morse code">Morse code</a> is an everyday example of a variable-length code with a comma. The long pauses between letters, and the even longer pauses between words, help people recognize where one letter (or word) ends, and the next begins. Similarly, <a href="Fibonacci_coding" title="Fibonacci coding">Fibonacci coding</a> uses a "11" to mark the end of every code word.

</p><p><a href="Self-synchronizing_code" title="Self-synchronizing code">Self-synchronizing codes</a> are prefix codes that allow <a href="Frame_synchronization" title="Frame synchronization">frame synchronization</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Related_concepts">Related concepts</h2></div>

<p>A <b>suffix code</b> is a set of words none of which is a suffix of any other; equivalently, a set of words which are the reverse of a prefix code. As with a prefix code, the representation of a string as a concatenation of such words is unique. A <b>bifix code</b> is a set of words which is both a prefix and a suffix code.<sup id="cite_ref-BPR58_8-0" class="reference"><a href="#cite_note-BPR58-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

An <b>optimal prefix code</b> is a prefix code with minimal average length. That is, assume an alphabet of <span class="texhtml mvar" style="font-style:italic;">n</span> symbols with probabilities <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(A_{i})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(A_{i})}</annotation>

</semantics>

</math></span><img src="./45b94a38a9fb8f45b36e53ac2471c414220549c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:5.611ex; height:2.843ex;" alt="{\displaystyle p(A_{i})}" loading="lazy"></span> for a prefix code <span class="texhtml mvar" style="font-style:italic;">C</span>. If <span class="texhtml mvar" style="font-style:italic;">C'</span> is another prefix code and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda '_{i}}">

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda '_{i}}</annotation>

</semantics>

</math></span><img src="./399e755010f10e78180554793999069332c0fecb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.155ex; height:2.843ex;" alt="{\displaystyle \lambda '_{i}}" loading="lazy"></span> are the lengths of the codewords of <span class="texhtml mvar" style="font-style:italic;">C'</span>, then <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{i=1}^{n}{\lambda _{i}p(A_{i})}\leq \sum _{i=1}^{n}{\lambda '_{i}p(A_{i})}\!}">

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=1}^{n}{\lambda _{i}p(A_{i})}\leq \sum _{i=1}^{n}{\lambda '_{i}p(A_{i})}\!}</annotation>

</semantics>

</math></span><img src="./80be495315f6931c4031be04fff29bb217a68698.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; margin-right: -0.166ex; width:25.715ex; height:6.843ex;" alt="{\displaystyle \sum _{i=1}^{n}{\lambda _{i}p(A_{i})}\leq \sum _{i=1}^{n}{\lambda '_{i}p(A_{i})}\!}" loading="lazy"></span>.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Prefix_codes_in_use_today">Prefix codes in use today</h2></div>

<p>Examples of prefix codes include:

</p>

<ul><li>variable-length <a href="Huffman_coding" title="Huffman coding">Huffman codes</a></li>

<li><a href="Country_calling_codes" class="mw-redirect" title="Country calling codes">country calling codes</a></li>

<li><a href="Chen%E2%80%93Ho_encoding" title="Chen–Ho encoding">Chen–Ho encoding</a></li>

<li>the country and publisher parts of <a href="ISBN" title="ISBN">ISBNs</a></li>

<li>the Secondary Synchronization Codes used in the <a href="UMTS" title="UMTS">UMTS</a> <a href="W-CDMA" class="mw-redirect" title="W-CDMA">W-CDMA</a> 3G Wireless Standard</li>

<li><a href="VCR_Plus" class="mw-redirect" title="VCR Plus">VCR Plus+ codes</a></li>

<li><a href="Unicode_Transformation_Format" class="mw-redirect" title="Unicode Transformation Format">Unicode Transformation Format</a>, in particular the <a href="UTF-8" title="UTF-8">UTF-8</a> system for encoding <a href="Unicode" title="Unicode">Unicode</a> characters, which is both a prefix-free code and a <a href="Self-synchronizing_code" title="Self-synchronizing code">self-synchronizing code</a><sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup></li>

<li><a href="Variable-length_quantity" title="Variable-length quantity">variable-length quantity</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="Techniques_2">Techniques</h3></div>

<p>Commonly used techniques for constructing prefix codes include <a href="Huffman_coding" title="Huffman coding">Huffman codes</a> and the earlier <a href="Shannon%E2%80%93Fano_coding" title="Shannon–Fano coding">Shannon–Fano codes</a>, and <a href="Universal_code_(data_compression)" title="Universal code (data compression)">universal codes</a> such as:

</p>

<ul><li><a href="Elias_delta_coding" title="Elias delta coding">Elias delta coding</a></li>

<li><a href="Elias_gamma_coding" title="Elias gamma coding">Elias gamma coding</a></li>

<li><a href="Elias_omega_coding" title="Elias omega coding">Elias omega coding</a></li>

<li><a href="Fibonacci_coding" title="Fibonacci coding">Fibonacci coding</a></li>

<li><a href="Levenshtein_coding" title="Levenshtein coding">Levenshtein coding</a></li>

<li><a href="Unary_coding" title="Unary coding">Unary coding</a></li>

<li><a href="Golomb_Rice_code" class="mw-redirect" title="Golomb Rice code">Golomb Rice code</a></li>

<li><a href="Straddling_checkerboard" title="Straddling checkerboard">Straddling checkerboard</a> (simple cryptography technique which produces prefix codes)</li>

<li>binary coding<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">US <a href="Federal_Standard_1037C" title="Federal Standard 1037C">Federal Standard 1037C</a></span>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation cs2"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20100708083829/http://www.atis.org/glossary/definition.aspx?id=6416"><i>ATIS Telecom Glossary 2007</i></a>, archived from <a rel="nofollow" class="external text" href="http://www.atis.org/glossary/definition.aspx?id=6416">the original</a> on July 8, 2010<span class="reference-accessdate">, retrieved <span class="nowrap">December 4,</span> 2010</span></cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFBerstelPerrin1985" class="citation cs2">Berstel, Jean; Perrin, Dominique (1985), <i>Theory of Codes</i>, Academic Press</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFGolombGordonWelch1958" class="citation cs2"><a href="Solomon_W._Golomb" title="Solomon W. Golomb">Golomb, S. W.</a>; <a href="Basil_Gordon" title="Basil Gordon">Gordon, Basil</a>; Welch, L. R. (1958), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=oRgtS14oa-sC&pg=PA202">"Comma-Free Codes"</a>, <i>Canadian Journal of Mathematics</i>, <b>10</b> (2): <span class="nowrap">202–</span>209, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.4153%2FCJM-1958-023-9">10.4153/CJM-1958-023-9</a></span>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:124092269">124092269</a></cite></span>

</li>

<li id="cite_note-LTU2015-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-LTU2015_5-0">^</a></b></span> <span class="reference-text">Le Boudec, Jean-Yves, Patrick Thiran, and Rüdiger Urbanke. Introduction aux sciences de l'information: entropie, compression, chiffrement et correction d'erreurs. PPUR Presses polytechniques, 2015.</span>

</li>

<li id="cite_note-BRS75-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-BRS75_6-0">^</a></b></span> <span class="reference-text">Berstel et al (2010) p.75</span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFA._Jones" class="citation web cs1">A. Jones, J. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110613183447/http://www.imperial.ac.uk/research/hep/group/theses/JJones.pdf">"Development of Trigger and Control Systems for CMS"</a> <span class="cs1-format">(PDF)</span>. High Energy Physics, Blackett Laboratory, Imperial College, London. p. 70. Archived from <a rel="nofollow" class="external text" href="http://www.imperial.ac.uk/research/hep/group/theses/JJones.pdf">the original</a> <span class="cs1-format">(PDF)</span> on Jun 13, 2011.</cite></span>

</li>

<li id="cite_note-BPR58-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-BPR58_8-0">^</a></b></span> <span class="reference-text">Berstel et al (2010) p.58</span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://www.cim.mcgill.ca/~langer/423/lecture2.pdf">McGill COMP 423 Lecture notes</a></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite id="CITEREFPike2003" class="citation web cs1">Pike, Rob (2003-04-03). <a rel="nofollow" class="external text" href="http://www.cl.cam.ac.uk/~mgk25/ucs/utf-8-history.txt">"UTF-8 history"</a>.</cite></span>

</li>

<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><cite id="CITEREFShevchuk2018" class="citation cs2">Shevchuk, Y. V. (2018), <a rel="nofollow" class="external text" href="http://psta.psiras.ru//read/psta2018_4_239-252.pdf">"Vbinary: variable length integer coding revisited"</a> <span class="cs1-format">(PDF)</span>, <i>Program Systems: Theory and Applications</i>, <b>9</b> (4): <span class="nowrap">239–</span>252, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.25209%2F2079-3316-2018-9-4-239-252">10.25209/2079-3316-2018-9-4-239-252</a></span></cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFBerstelPerrinReutenauer2010" class="citation book cs1">Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). <a rel="nofollow" class="external text" href="http://www-igm.univ-mlv.fr/~berstel/LivreCodes/Codes.html"><i>Codes and automata</i></a>. Encyclopedia of Mathematics and its Applications. Vol. 129. Cambridge: <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-88831-8</bdi>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1187.94001">1187.94001</a>.</cite></li>

<li><cite id="CITEREFElias1975" class="citation journal cs1"><a href="Peter_Elias" title="Peter Elias">Elias, Peter</a> (1975). "Universal codeword sets and representations of the integers". <i>IEEE Trans. Inf. Theory</i>. <b>21</b> (2): <span class="nowrap">194–</span>203. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Ftit.1975.1055349">10.1109/tit.1975.1055349</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0018-9448">0018-9448</a>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:0298.94011">0298.94011</a>.</cite></li>

<li>D.A. Huffman, "A method for the construction of minimum-redundancy codes", Proceedings of the I.R.E., Sept. 1952, pp. 1098–1102 (Huffman's original article)</li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20070220234037/http://www.huffmancoding.com/david/scientific.html">Profile: David A. Huffman</a>, <a href="Scientific_American" title="Scientific American">Scientific American</a>, Sept. 1991, pp. 54–58 (Background story)</li>

<li><a href="Thomas_H._Cormen" title="Thomas H. Cormen">Thomas H. Cormen</a>, <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Charles E. Leiserson</a>, <a href="Ronald_L._Rivest" class="mw-redirect" title="Ronald L. Rivest">Ronald L. Rivest</a>, and <a href="Clifford_Stein" title="Clifford Stein">Clifford Stein</a>. <i><a href="Introduction_to_Algorithms" title="Introduction to Algorithms">Introduction to Algorithms</a></i>, Second Edition. MIT Press and McGraw-Hill, 2001. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-262-03293-7</bdi>. Section 16.3, pp. 385–392.</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output .citation{word-wrap:break-word}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}

/* end https://en.wikipedia.org/ */

</style><span class="citation 1037C"><span class="noviewer" typeof="mw:File"><span></span></span> This article incorporates <a href="Copyright_status_of_works_by_the_federal_government_of_the_United_States" title="Copyright status of works by the federal government of the United States">public domain material</a> from <cite class="citation cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20220122224547/https://www.its.bldrdoc.gov/fs-1037/fs-1037c.htm"><i>Federal Standard 1037C</i></a>. <a href="General_Services_Administration" title="General Services Administration">General Services Administration</a>. Archived from <a rel="nofollow" class="external text" href="https://www.its.bldrdoc.gov/fs-1037/fs-1037c.htm">the original</a> on 2022-01-22.</cite></span></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://plus.maths.org/issue10/features/infotheory/index.html">Codes, trees and the prefix property</a> by Kona Macphee</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Data_compression_methods241" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Data_compression_methods241" style="font-size:114%;margin:0 4em"><a href="Data_compression" title="Data compression">Data compression</a> methods</div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Lossless_compression" title="Lossless compression">Lossless</a><br>type</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Entropy_coding" title="Entropy coding">Entropy</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Adaptive_coding" title="Adaptive coding">Adaptive coding</a></li>

<li><a href="Arithmetic_coding" title="Arithmetic coding">Arithmetic</a></li>

<li><a href="Asymmetric_numeral_systems" title="Asymmetric numeral systems">Asymmetric numeral systems</a></li>

<li><a href="Golomb_coding" title="Golomb coding">Golomb</a></li>

<li><a href="Huffman_coding" title="Huffman coding">Huffman</a>

<ul><li><a href="Adaptive_Huffman_coding" title="Adaptive Huffman coding">Adaptive</a></li>

<li><a href="Canonical_Huffman_code" title="Canonical Huffman code">Canonical</a></li>

<li><a href="Modified_Huffman_coding" title="Modified Huffman coding">Modified</a></li></ul></li>

<li><a href="Range_coding" title="Range coding">Range</a></li>

<li><a href="Shannon_coding" title="Shannon coding">Shannon</a></li>

<li><a href="Shannon%E2%80%93Fano_coding" title="Shannon–Fano coding">Shannon–Fano</a></li>

<li><a href="Shannon%E2%80%93Fano%E2%80%93Elias_coding" title="Shannon–Fano–Elias coding">Shannon–Fano–Elias</a></li>

<li><a href="Tunstall_coding" title="Tunstall coding">Tunstall</a></li>

<li><a href="Unary_coding" title="Unary coding">Unary</a></li>

<li><a href="Universal_code_(data_compression)" title="Universal code (data compression)">Universal</a>

<ul><li><a href="Exponential-Golomb_coding" title="Exponential-Golomb coding">Exp-Golomb</a></li>

<li><a href="Fibonacci_coding" title="Fibonacci coding">Fibonacci</a></li>

<li><a href="Elias_gamma_coding" title="Elias gamma coding">Gamma</a></li>

<li><a href="Levenshtein_coding" title="Levenshtein coding">Levenshtein</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Dictionary_coder" title="Dictionary coder">Dictionary</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Byte-pair_encoding" title="Byte-pair encoding">Byte-pair encoding</a></li>

<li><a href="LZ77_and_LZ78" title="LZ77 and LZ78">Lempel–Ziv</a>

<li><a href="Snappy_(compression)" title="Snappy (compression)">Snappy</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Delta_encoding" title="Delta encoding">Delta</a>

<ul><li><a href="Incremental_encoding" title="Incremental encoding">Incremental</a></li></ul></li>

<li><a href="Grammar-based_code" title="Grammar-based code">Grammar</a>

<li><a href="Sequitur_algorithm" title="Sequitur algorithm">Sequitur</a></li></ul></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Hybrid</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>LZ77 + Huffman

<ul><li><a href="Deflate" title="Deflate">Deflate</a></li>

<li>LZ77 + ANS

<ul><li><a href="LZFSE" title="LZFSE">LZFSE</a></li></ul></li>

<li>LZ77 + Huffman + ANS

<ul><li><a href="Zstd" title="Zstd">Zstandard</a></li></ul></li>

<li>LZ77 + Huffman + context

<ul><li><a href="Brotli" title="Brotli">Brotli</a></li></ul></li>

<li>LZSS + Huffman

<li>LZ77 + Range

<li>LZHAM</li></ul></li>

<li>RLE + BWT + MTF + Huffman

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Lossy_compression" title="Lossy compression">Lossy</a><br>type</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Transform_coding" title="Transform coding">Transform</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Discrete_cosine_transform" title="Discrete cosine transform">Discrete cosine transform</a>

<li><a href="Wavelet_transform" title="Wavelet transform">Wavelet</a>

<ul><li><a href="Daubechies_wavelet" title="Daubechies wavelet">Daubechies</a></li>

<li><a href="Set_partitioning_in_hierarchical_trees" title="Set partitioning in hierarchical trees">SPIHT</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Predictive</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Adaptive_differential_pulse-code_modulation" title="Adaptive differential pulse-code modulation">ADPCM</a></li></ul></li>

<ul><li><a href="Algebraic_code-excited_linear_prediction" title="Algebraic code-excited linear prediction">ACELP</a></li>

<li>Motion

<ul><li><a href="Motion_compensation" title="Motion compensation">Compensation</a></li>

<li><a href="Motion_estimation" title="Motion estimation">Estimation</a></li>

<li><a href="Motion_vector" class="mw-redirect" title="Motion vector">Vector</a></li></ul></li>

<li><a href="Psychoacoustics" title="Psychoacoustics">Psychoacoustic</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Data_compression#Audio" title="Data compression">Audio</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Concepts</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Companding" title="Companding">Companding</a></li>

<li><a href="Convolution" title="Convolution">Convolution</a></li>

<li><a href="Dynamic_range" title="Dynamic range">Dynamic range</a></li>

<li><a href="Latency_(audio)" title="Latency (audio)">Latency</a></li>

<li><a href="Nyquist%E2%80%93Shannon_sampling_theorem" title="Nyquist–Shannon sampling theorem">Nyquist–Shannon theorem</a></li>

<li><a href="Sampling_(signal_processing)" title="Sampling (signal processing)">Sampling</a></li>

<li><a href="Silence_compression" title="Silence compression">Silence compression</a></li>

<li><a href="Sound_quality" title="Sound quality">Sound quality</a></li>

<li><a href="Speech_coding" title="Speech coding">Speech coding</a></li>

<li><a href="Sub-band_coding" title="Sub-band coding">Sub-band coding</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Audio_codec" title="Audio codec">Codec</a><br>parts</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Adaptive_differential_pulse-code_modulation" title="Adaptive differential pulse-code modulation">ADPCM</a></li>

<ul><li><a href="Algebraic_code-excited_linear_prediction" title="Algebraic code-excited linear prediction">ACELP</a></li>

<li><a href="Psychoacoustics" title="Psychoacoustics">Psychoacoustic model</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Image_compression" title="Image compression">Image</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Concepts</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Chroma_subsampling" title="Chroma subsampling">Chroma subsampling</a></li>

<li><a href="Coding_tree_unit" title="Coding tree unit">Coding tree unit</a></li>

<li><a href="Color_space" title="Color space">Color space</a></li>

<li><a href="Compression_artifact" title="Compression artifact">Compression artifact</a></li>

<li><a href="Image_resolution" title="Image resolution">Image resolution</a></li>

<li><a href="Macroblock" title="Macroblock">Macroblock</a></li>

<li><a href="Pixel" title="Pixel">Pixel</a></li>

<li><a href="Quantization_(image_processing)" title="Quantization (image processing)">Quantization</a></li>

<li><a href="Standard_test_image" title="Standard test image">Standard test image</a></li>

<li><a href="Texture_compression" title="Texture compression">Texture compression</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Methods</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Chain_code" title="Chain code">Chain code</a></li>

<li><a href="Deflate" title="Deflate">Deflate</a></li>

<li><a href="Fractal_compression" title="Fractal compression">Fractal</a></li>

<li><a href="Wavelet_transform" title="Wavelet transform">Wavelet</a>

<ul><li><a href="Daubechies_wavelet" title="Daubechies wavelet">Daubechies</a></li>

<li><a href="Set_partitioning_in_hierarchical_trees" title="Set partitioning in hierarchical trees">SPIHT</a></li></ul></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Data_compression#Video" title="Data compression">Video</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Concepts</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Display_resolution" title="Display resolution">Display resolution</a></li>

<li><a href="Film_frame" title="Film frame">Frame</a></li>

<li><a href="Frame_rate" title="Frame rate">Frame rate</a></li>

<li><a href="Video_compression_picture_types" title="Video compression picture types">Frame types</a></li>

<li><a href="Interlaced_video" title="Interlaced video">Interlace</a></li>

<li><a href="Video#Characteristics_of_video_streams" title="Video">Video characteristics</a></li>

<li><a href="Video_quality" title="Video quality">Video quality</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Video_codec" title="Video codec">Codec</a><br>parts</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Deblocking_filter" title="Deblocking filter">Deblocking filter</a></li>

<li><a href="Lapped_transform" title="Lapped transform">Lapped transform</a></li>

<li>Motion

<ul><li><a href="Motion_compensation" title="Motion compensation">Compensation</a></li>

<li><a href="Motion_estimation" title="Motion estimation">Estimation</a></li>

<li><a href="Motion_vector" class="mw-redirect" title="Motion vector">Vector</a></li></ul></li>

<li><a href="Wavelet_transform" title="Wavelet transform">Wavelet</a>

<ul><li><a href="Daubechies_wavelet" title="Daubechies wavelet">Daubechies</a></li>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Information_theory" title="Information theory">Theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Compressed_data_structure" title="Compressed data structure">Compressed data structures</a>

<ul><li><a href="Compressed_suffix_array" title="Compressed suffix array">Compressed suffix array</a></li>

<li><a href="FM-index" title="FM-index">FM-index</a></li></ul></li>

<li><a href="Entropy_(information_theory)" title="Entropy (information theory)">Entropy</a></li>

<li><a href="Information_theory" title="Information theory">Information theory</a>

<ul><li><a href="Timeline_of_information_theory" title="Timeline of information theory">Timeline</a></li></ul></li>

<li><a href="Kolmogorov_complexity" title="Kolmogorov complexity">Kolmogorov complexity</a></li>

<li><a href="Quantization_(signal_processing)" title="Quantization (signal processing)">Quantization</a></li>

<li><a href="Rate%E2%80%93distortion_theory" title="Rate–distortion theory">Rate–distortion</a></li>

<li><a href="Redundancy_(information_theory)" title="Redundancy (information theory)">Redundancy</a></li>

<li><a href="Data_compression_symmetry" title="Data compression symmetry">Symmetry</a></li>

<li><a href="Smallest_grammar_problem" title="Smallest grammar problem">Smallest grammar problem</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Community</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Hutter_Prize" title="Hutter Prize">Hutter Prize</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">People</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Mark_Adler" title="Mark Adler">Mark Adler</a></li>

</div></td></tr></tbody></table></div> </div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-12" href="https://en.wikipedia.org/wiki/?title=Prefix_code&oldid=1290037680">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>